package com.lee.datastructures.tree;

import java.util.Comparator;


/**
 * bstree
 *
 * @author winston
 * @date 2022/05/09
 */
public class BSTree<T extends Comparable<T>>{

    private BSTNode<T> mRoot;

    public class BSTNode<T extends Comparable<T>> {
        T value;
        BSTNode<T> left;
        BSTNode<T> right;
        BSTNode<T> parent;

        public BSTNode(T key, BSTNode<T> left, BSTNode<T> right, BSTNode<T> parent) {
            this.value = key;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    }

    public BSTNode<T> getmRoot() {
        return mRoot;
    }

    public void setmRoot(BSTNode<T> mRoot) {
        this.mRoot = mRoot;
    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(mRoot);
    }

    private void preOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value+" ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(mRoot);
    }

    public void inOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.value+" ");
        inOrder(node.right);

    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(mRoot);
    }

    private void postOrder(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value+" ");
    }


    /**
     * 递归搜索树
     *
     * @param node  节点
     * @param value 价值
     * @return {@link BSTNode}<{@link T}>
     */
    public BSTNode<T> search(BSTNode<T> node, T value) {
        if (node == null) {
            return null;
        }

        int temp = node.value.compareTo(value);
        if (temp > 0) {
            return search(node.left, value);
        } else if (temp < 0) {
            return search(node.right, value);
        } else {
            return node;
        }
    }

    /**
     * 迭代器搜索
     *
     * @param node  节点
     * @param value 价值
     * @return {@link BSTNode}<{@link T}>
     */
    public BSTNode<T> iteratorSearch(BSTNode<T> node, T value) {
        if (node == null) {
            return node;
        }
        while (node != null) {
            int cmp = node.value.compareTo(value);
            if (cmp > 0) {
                node = node.left;
            } else if (cmp < 0) {
                node = node.right;
            } else {
                return node;
            }
        }
        return node;
    }

    /**
     * 最大节点
     *
     * @param node 节点
     * @return {@link BSTNode}<{@link T}>
     */
    private BSTNode<T> max(BSTNode<T> node) {
        if (node == null) {
            return node;
        }

        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    public BSTNode<T> max() {
        return max(mRoot);
    }

    /**
     * 最小节点
     *
     * @param node 节点
     * @return {@link BSTNode}<{@link T}>
     */
    private BSTNode<T> min(BSTNode<T> node) {
        if (node == null) {
            return node;
        }

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public BSTNode<T> min() {
        return min(this.mRoot);
    }

    /**
     * 前任, 小于该节点的最大节点.
     * 即: 左节点为根的最大节点.
     *
     * 如果没有左孩子, 取最近的有右孩子的父节点
     *
     * @param x x
     * @return {@link BSTNode}<{@link T}>
     */
    public BSTNode<T> predecessor(BSTNode<T> x) {
//        左节点为根的最大节点.
        if (x.left != null) {
            return max(x.left);
        }

        BSTNode<T> p = x.parent;
        while (p.right != null && (x == p.left)) {
            x = p;
            p = p.parent;
        }
        return p;
    }

    /**
     * 继任者,
     * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
     *
     * @param x x
     * @return {@link BSTNode}<{@link T}>
     */
    public BSTNode<T> successor(BSTNode<T> x) {

// 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
        if (x.right != null)
            return min(x.right);

        // 如果x没有右孩子。则x有以下两种可能:
        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
        BSTNode<T> y = x.parent;
        while ((y!=null) && (x==y.right)) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    private void insert(BSTree<T> tree, BSTNode<T> newNode) {
        BSTNode<T> init = tree.mRoot;
        BSTNode<T> parent = null;

        // 找到newNode的父节点,
        while (init != null) {
            parent = init;
            int cmp = newNode.value.compareTo(parent.value);
            if (cmp < 0) {
                init = init.left;
            } else {
                init = init.right;
            }
        }
        newNode.parent = parent;

        // 如果parent为null, 说明是个空树, 直接作为根节点.
        if (parent == null) {
            tree.mRoot = newNode;
            // 将新节点置为找到的父节点的左/右子节点.
        } else {
            int tmp = newNode.value.compareTo(parent.value);
            if (tmp < 0) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
        }
    }

    public void insert(T key) {
        BSTNode<T> node = new BSTNode<>(key, null, null, null);
        insert(this, node);
    }

    /**
     * 删除节点
     *
     * @param tree 树
     * @param node 节点
     * @return {@link BSTNode}<{@link T}>
     */
    private BSTNode<T> deleteNode(BSTree<T> tree, BSTNode<T> node) {
//        如果要删除的节点只有左孩子，那么就让该节点的父亲结点指向该节点的左孩子，
//        如何判断当前节点是父节点的什么节点? 左/右, 遍历?
//        然后删除该节点，返回true；
//        if (node.left != null && node.right == null) {
//            if(node.equals(node.parent.left)) {
//                node.parent.left = node.left;
//            }else {
//                node.parent.right = node.left;
//            }
//            node.left.parent = node.parent;
//            node.left=null;
//            node.right=null;
//            node.parent=null;
//            return node;
//        }
////        如果要删除的节点只有右孩子，那么就让该节点的父亲结点指向该节点的右孩子，然后删除该节点，返回true；
//        if (node.right != null && node.left == null) {
//            if(node.equals(node.parent.left)) {
//                node.parent.left = node.right;
//            }else {
//                node.parent.right = node.right;
//            }
//            node.right.parent = node.parent;
//            node.left=null;
//            node.right=null;
//            node.parent=null;
//            return node;
//        }
////        最后一种也是最麻烦的一种就是要删除的节点的左右孩子都存在。此时我们的删除方法如下：
////        1, 找到该节点的 后驱节点
////        2、把后驱节点的值和要删除的节点的值进行交换
////        3、然后删除这个节点即相当于把我们想删除的节点删除了，返回true；
//        if (node.left != null && node.right != null) {
//            BSTNode<T> successor = successor(node);
//            node.value=successor.value;
//            if(node.right)
//        }

        // 先判断目标节点的形态: 分为有0-1个,或者2个孩子节点.
        // 为0-1个孩子时, 直接让, 直接让存在的孩子代替被删除的孩子的位置即可. 为null也正确
        // 有两个孩子时, 让后驱节点代替当前节点, 后驱节点的孩子交给后驱节点的父节点.
        // 然后把被删除的节点的值换成找到的节点的值

        // 实现步骤: 1. 找到替换节点
        BSTNode<T> switchNode = null;
        if (node.left == null || node.right == null) {
            switchNode = node;
        }else {
            switchNode = successor(node);
        }

        BSTNode<T> child = null;
        if (switchNode.left == null) {
            child = switchNode.right;
        } else {
            child = switchNode.left;
        }

        // 先把child的parent修改为switchNode的parent
        if (child != null) {
            child.parent = switchNode.parent;
        }

        // 如果没有父节点, 说明这个节点是根节点.
        if (switchNode.parent == null) {
            mRoot = switchNode;
        } else if (switchNode.parent.left == switchNode) {
            switchNode.parent.left = child;
        } else {
            switchNode.parent.right = child;
        }

        node.value = switchNode.value;
        return node;
    }

    public void deleteNode(T key) {
        BSTNode<T> node = search(mRoot, key);
        if (node == null) {
            return;
        }
        deleteNode(this, node);
    }

    private void destory(BSTNode<T> node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            destory(node.left);
        }
        if (node.right != null) {
            destory(node.right);
        }
        node = null;
    }

    public void destory() {
        destory(mRoot);
    }

}
